package com.husk.leetcode.basic;

import com.alibaba.fastjson.JSON;
import org.junit.Test;

import java.util.*;
import java.util.stream.Collectors;

/**
 * <p>
 *
 * </p>
 *
 * @author hushunke@foxmail.com
 * @since 2021/7/16
 */
public class Solution2 {

    /**
     * 剑指 Offer 53 - I. 在排序数组中查找数字 I
     * <p>
     * https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
     */
    public int search(int[] nums, int target) {
        int result = 0;
        boolean flag = false;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                result++;
                flag = true;
            }
            if (flag && nums[i] != target) {
                break;
            }
        }
        return result;
    }

    public int binarySearch(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int mid = 0, result = 0;
        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[mid] == target) {
                result = 1;
                break;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            }
        }
        if (result == 0) {
            return result;
        }
        for (int i = mid - 1; i >= 0 && nums[i] == target; i--, result++) ;
        for (int i = mid + 1; i < nums.length && nums[i] == target; i++, result++) ;
        return result;
    }


    /**
     * 面试题 10.02. 变位词组
     * https://leetcode-cn.com/problems/group-anagrams-lcci/
     *
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            List<String> list = map.get(key);
            if (Objects.isNull(list)) {
                list = new ArrayList<>();
                map.put(key, list);
            }
            list.add(str);
        }
        return new ArrayList<>(map.values());
    }

    /**
     * 409. 最长回文串
     * https://leetcode-cn.com/problems/longest-palindrome/
     *
     * @param s
     * @return
     */
    public int longestPalindrome(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            Integer count = map.get(ch);
            if (count == null) {
                map.put(ch, 1);
            } else {
                map.put(ch, ++count);
            }
        }
        int ans = 0;
        for (Integer item : map.values()) {
            ans += item / 2 * 2;
            if (item % 2 == 1 && ans % 2 == 0) {
                ans++;
            }
        }
        return ans;
    }

    public boolean isCovered(int[][] ranges, int left, int right) {
        Set<Integer> numbers = new HashSet<>();
        for (int i = 0; i < ranges.length; i++) {
            for (int j = ranges[i][0]; j <= ranges[i][1]; j++) {
                numbers.add(j);
            }
        }
        for (int i = left; i <= right; i++) {
            if (!numbers.contains(i)) {
                return false;
            }
        }
        return true;
    }

    public int titleToNumber(String columnTitle) {
        int number = 0;
        int multiple = 1;
        for (int i = columnTitle.length() - 1; i >= 0; i--) {
            int num = columnTitle.charAt(i) - 'A' + 1;
            number += num * multiple;
            multiple = multiple * 26;
        }
        return number;
    }

    public String maximumTime(String time) {
        char[] charArray = time.toCharArray();
        if (charArray[0] == '?') {
            charArray[0] = (charArray[1] >= '4' && charArray[1] <= '9') ? '1' : '2';
        }
        if (charArray[1] == '?') {
            charArray[1] = charArray[0] == '2' ? '3' : '9';
        }
        if (charArray[3] == '?') {
            charArray[3] = '5';
        }
        if (charArray[4] == '?') {
            charArray[4] = '9';
        }
        return new String(charArray);
    }

    public String convertToBase7(int num) {
        boolean positive = num >= 0;
        int data = Math.abs(num);
        StringBuilder sb = new StringBuilder();
        while (true) {
            int a = data / 7;
            int mod = data % 7;
            sb.append(mod);
            if (a == 0) {
                break;
            }
            data = a;
        }
        if (!positive) {
            sb.append("-");
        }
        return sb.reverse().toString();
    }

    /**
     * 581. 最短无序连续子数组
     * https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/
     *
     * @param nums
     * @return
     */
    public int findUnsortedSubarray(int[] nums) {
        boolean isSorted = true;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i - 1] > nums[i]) {
                isSorted = false;
                break;
            }
        }
        if (isSorted) {
            return 0;
        }

        int[] numsSorted = new int[nums.length];
        System.arraycopy(nums, 0, numsSorted, 0, nums.length);
        Arrays.sort(numsSorted);
        int left = 0;
        while (nums[left] == numsSorted[left]) {
            left++;
        }
        int right = nums.length - 1;
        while (nums[right] == numsSorted[right]) {
            right--;
        }
        return right - left + 1;
    }

    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        String s = String.valueOf(x);
        for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 6. Z 字形变换
     * https://leetcode-cn.com/problems/zigzag-conversion/
     *
     * @param s
     * @param numRows
     * @return
     */
    public String convert(String s, int numRows) {
        if (s.length() == 1 || numRows == 1) {
            return s;
        }
        String[] stringArray = new String[numRows];
        Arrays.fill(stringArray, "");

        // 这周期，2n-2，为一组
        int period = numRows * 2 - 2;

        for (int i = 0; i < s.length(); i++) {
            int mod = i % period;
            if (mod < numRows) {
                stringArray[mod] += s.charAt(i);
            } else {
                stringArray[period - mod] += s.charAt(i);
            }
        }
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < stringArray.length; i++) {
            ans.append(stringArray[i]);
        }
        return ans.toString();
    }

    /**
     * 14. 最长公共前缀
     * https://leetcode-cn.com/problems/longest-common-prefix/
     *
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {
        int min = Arrays.stream(strs).mapToInt(String::length).min().getAsInt();
        StringBuilder ans = new StringBuilder();

        POINT:
        for (int i = 0; i < min; i++) {
            char charactor = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if (strs[j].charAt(i) != charactor) {
                    break POINT;
                }
            }
            ans.append(charactor);
        }
        return ans.toString();
    }

    /**
     * 167. 两数之和 II - 输入有序数组
     * https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
     *
     * @param numbers
     * @param target
     * @return
     */
    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length - 1; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[i] + numbers[j] == target) {
                    return new int[]{numbers[i], numbers[j]};
                }
            }
        }
        return null;
    }

    // 双指针
    public int[] twoSum2(int[] numbers, int target) {
        int i = 0, j = numbers.length - 1;
        while (i < j) {
            int sum = numbers[i] + numbers[j];
            if (sum > target) {
                j--;
            } else if (sum < target) {
                i++;
            } else {
                return new int[]{i + 1, j + 1};
            }
        }
        return null;
    }

    /**
     * 611. 有效三角形的个数
     * https://leetcode-cn.com/problems/valid-triangle-number/
     *
     * @param nums
     * @return
     */
    public int triangleNumber(int[] nums) {
        // 固定2个最小边，查满足条件的第三个边
        Arrays.sort(nums);
        int ans = 0;
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                int left = j + 1;
                int right = n - 1;
                while (left <= right) {
                    int mid = (left + right) / 2;
                    if (nums[mid] < nums[i] + nums[j]) {
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
                ans += right - j;
            }
        }
        return ans;
    }

    public int[] runningSum(int[] nums) {
        int[] ans = new int[nums.length];
        ans[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            ans[i] = ans[i - 1] + nums[i];
        }
        return ans;
    }

    /**
     * 22. 括号生成
     * https://leetcode-cn.com/problems/generate-parentheses/
     *
     * @param n
     * @return
     */
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        char[] chars = new char[n * 2];
        Arrays.fill(chars, '(');


        return ans;
    }

    private boolean isValid(char[] chars) {
        int balance = 0;
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            if (c == '(') {
                balance++;
            } else {
                balance--;
            }
            if (balance < 0) {
                return false;
            }
        }
        return balance == 0;
    }


    public int sumOddLengthSubarrays(int[] arr) {
        List<List<Integer>> ans = new ArrayList<>();
        for (int length = 1; length <= arr.length; length += 2) {
            for (int start = 0; start + length <= arr.length; start++) {
                List<Integer> list = new ArrayList<>();
                for (int i = start; i < start + length; i++) {
                    list.add(arr[i]);
                }
                ans.add(list);
            }
        }
        return ans.stream().flatMap(Collection::stream).reduce(Integer::sum).orElse(0);
    }

    /**
     * 498. 对角线遍历
     * https://leetcode-cn.com/problems/diagonal-traverse/
     *
     * @param mat
     * @return
     */
    public int[] findDiagonalOrder(int[][] mat) {
        /**
         * 00
         * 01 10
         * 02 11 20
         * 03 12 21 30
         * 04 13 22 31
         * 14 23 32
         * 24 33
         * 34
         *
         */
        if (mat == null || mat.length == 0) {
            return new int[0];
        }
        int x = mat[0].length;
        int y = mat.length;

        int[] ans = new int[x * y];
        int index = 0;

        boolean reverse = true;
        for (int i = 0; i <= x + y - 2; i++) {
            if (!reverse) {
                for (int k = 0; k <= i; k++) {
                    if (k >= y || i - k >= x) {
                        continue;
                    }
                    ans[index] = mat[k][i - k];
                    index++;
                }
            } else {
                for (int k = i; k >= 0; k--) {
                    if (k >= y || i - k >= x) {
                        continue;
                    }
                    ans[index] = mat[k][i - k];
                    index++;
                }
            }
            reverse = !reverse;
        }
        return ans;
    }

    /**
     * 984. 不含 AAA 或 BBB 的字符串
     * https://leetcode-cn.com/problems/string-without-aaa-or-bbb/
     *
     * @param a
     * @param b
     * @return
     */
    public String strWithout3a3b(int a, int b) {
        StringBuilder ans = new StringBuilder();
        while (a > 0 || b > 0) {
            int l = ans.length();
            if (l >= 2 && ans.charAt(l - 1) == ans.charAt(l - 2)) {
                if (ans.charAt(l - 1) == 'a') {
                    ans.append("b");
                    b--;
                } else {
                    ans.append("a");
                    a--;
                }
            } else {
                if (a >= b) {
                    ans.append("a");
                    a--;
                } else {
                    ans.append("b");
                    b--;
                }
            }
        }
        return ans.toString();
    }

    @Test
    public void test() {
        System.out.println(this.strWithout3a3b(4, 1));
    }


}
